Semi%2Dsupervised Density%2DBased Clustering.

Decomposing object%2Doriented class modules using an agglomerative clustering technique.
Software can be considered a live entity, as it undergoes many alterations throughout its lifecycle. Furthermore, developers do not usually retain a good design in favor of adding new features, comply with requirements or meet deadlines. For these reasons, code can become rather complex and difficult to understand. More particularly in object-oriented systems, classes may become very large and less cohesive. In order to identify such problematic cases, existing approaches have proposed the use of cohesion metrics. However, while metrics can identify classes with low cohesion, they cannot identify new or independent concepts. Moreover, these methods require a lot of human interpretation to identify the respective design flaws. In this paper, we propose a class decomposition method using an agglomerative clustering algorithm based on the Jaccard distance between class members. Our methodology is able to identify new concepts and rank the solutions according to their impact on the design quality of the system. Finally, our method has been evaluated by two independent designers who were asked to comment on the suggestions produced by our technique on their projects. The designers provided feedback on the ability of the method to identify new concepts and improve the design quality of the system in terms of cohesion. 1.
Subspace and projected clustering experimental evaluation and analysis.

Finding non%2Dredundant
Many approaches have been proposed to find correlations in binary data. Usually, these methods focus on pair-wise correlations. In biology applications, it is important to find correlations that involve more than just two features. Moreover, a set of strongly correlated features should be non-redundant in the sense that the correlation is strong only when all the interacting features are considered together. Removing any feature will greatly reduce the correlation. In this paper, we explore the problem of finding non-redundant high order correlations in binary data. The high order correlations are formalized using multi-information, a generalization of pairwise mutual information. To reduce the redundancy, we require any subset of a strongly correlated feature subset to be weakly correlated. Such feature subsets are referred to as Non-redundant Interacting Feature Subsets (NIFS). Finding all NIFSs is computationally challenging, because in addition to enumerating feature combinations, we also need to check all their subsets for redundancy. We study several properties of NIFSs and show that these properties are useful in developing efficient algorithms. We further develop two sets of upper and lower bounds on the correlations, which can be incorporated in the algorithm to prune the search space. A simple and effective pruning strategy based on pair-wise mutual information is also developed to further prune the search space. The efficiency and effectiveness of our approach are demonstrated through extensive experiments on synthetic and real-life datasets. 1.
PIST An Efficient and Practical Indexing Technique for Historical Spatio%2DTemporal Point Data.

Robust projected clustering.

On Join Location in Sensor Networks.
We consider the problem of processing join queries in a wireless sensor network, focusing on where (which sensor node(s)) to process the join. We propose four strategies for processing such queries and investigate their performance across several scenarios. Not surprisingly, our experiments show that no single strategy performs best for all scenarios. In order to avoid the potential high cost of using a fixed strategy for processing all queries, we develop a cost-based model that can be used to select the best join strategy for the query at hand. Our experiments confirm that, given a set of queries, selecting the join strategy based on the cost model is always better than using any fixed strategy for all queries. 1.
Effective Summarization of Multi%2DDimensional Data Streams for Historical Stream Mining.

Adaptive processing of historical spatial range queries in peer%2Dto%2Dpeer sensor networks.

Efficient composite pattern finding from monad patterns.

A Classification%2DBased Glioma Diffusion Model Using MRI Data.

Speedup Clustering with Hierarchical Ranking.

P3C A Robust Projected Clustering Algorithm.

Learning a Classification%2Dbased Glioma Growth Model Using MRI Data.

cisRED a database system for genome%2Dscale computational discovery of regulatory elements.

Exploiting redundancy in sensor networks for energy efficient processing of spatiotemporal region queries.
Sensor networks are made of autonomous devices that are able to collect, store, process and share data with other devices. Spatiotemporal region queries can be used for retrieving information of interest from such networks. Such queries require the answers only from the subset of the network nodes that fall into the query region. If the network is redundant in the sense that the measurements of some nodes can be substituted by those of other nodes with a certain degree of confidence, then a much smaller subset of nodes may be sufficient to answer the query at a lower energy cost. We investigate how to take advantage of such data redundancy and propose two techniques to process spatiotemporal region queries under these conditions. Our techniques reduce up to twenty times the energy cost of query processing compared to the typical network flooding, thus prolonging the lifetime of the sensor network.
Segmenting Brain Tumors with Conditional Random Fields and Support Vector Machines.
Abstract. Markov Random Fields (MRFs) are a popular and wellmotivated model for many medical image processing tasks such as segmentation. Discriminative Random Fields (DRFs), a discriminative alternative to the traditionally generative MRFs, allow tractable computation with less restrictive simplifying assumptions, and achieve better performance in many tasks. In this paper, we investigate the tumor segmentation performance of a recent variant of DRF models that takes advantage of the powerful Support Vector Machine (SVM) classification method. Combined with a powerful Magnetic Resonance (MR) preprocessing pipeline and a set of ‘alignment-based ’ features, we evaluate the use of SVMs, MRFs, and two types of DRFs as classifiers for three segmentation tasks related to radiation therapy target planning for brain tumors, two of which do not rely on ‘contrast agent ’ enhancement. Our results indicate that the SVM-based DRFs offer a significant advantage over the other approaches. 1
An Analysis of Spatio%2DTemporal Query Processing in Sensor Networks.
Sensor networks are an emerging technology that provide new means to monitor and understand various phenomena. Nodes in a sensor network typically have a limited power supply, thus energy-efficient processing of the queries over the network is a critical issue. We propose analytical models to evaluate the performance of three methods for processing historical spatio-temporal queries in sensor networks. The models allow us to better understand the tradeoffs of the investigated method, as well as to recommend the most energy efficient one at query time. 1.
A Trajectory Splitting Model for Efficient Spatio%2DTemporal Indexing.
This paper addresses the problem of splitting trajectories optimally for the purpose of efficiently supporting spatio-temporal range queries using index structures (e.g., R-trees) that use minimum bounding hyper-rectangles as trajectory approximations. We derive a formal cost model for estimating the number of I/Os required to evaluate a spatio-temporal range query with respect to a given query size and an arbitrary split of a trajectory. Based on the proposed model, we introduce a dynamic programming algorithm for splitting a set of trajectories that minimizes the number of expected disk I/Os with respect to an average query size. In addition, we develop a linear time, near optimal solution for this problem to be used in a dynamic case where trajectory points are continuously updated. Our experimental evaluation confirms the effectiveness and efficiency of our proposed splitting policies when embedded into an R-tree structure. 1.
A methodology for analyzing SAGE libraries for cancer profiling.
Serial Analysis of Gene Expression (SAGE) has proven to be an important alternative to microarray techniques for global profiling of mRNA populations. We have developed preprocessing methodologies to address problems in analyzing SAGE data due to noise caused by sequencing error, normalization methodologies to account for libraries sampled at different depths, and missing tag imputation methodologies to aid in the analysis of poorly sampled SAGE libraries. We have also used subspace selection using the Wilcoxon rank sum test to exclude tags that have similar expression levels regardless of source. Using these methodologies we have clustered, using the OPTICS algorithm, 88 SAGE libraries derived from cancerous and normal tissues as well as cell line material. Our results produced eight dense clusters representing ovarian cancer cell line, brain cancer cell line, brain cancer bulk tissue, prostate tissue, pancreatic cancer, breast cancer cell line, normal brain, and normal breast bulk tissue. The ovarian cancer and brain cancer cell lines clustered closely together, leading to a further investigation on possible associations between these two cancer types. We also investigated the utility of gene expression data in the classification between normal and cancerous tissues. Our results indicate that brain and breast cancer libraries have strong identities allowing robust discrimination from their normal counterparts. However, the SAGE expression
Spatio%2DTemporal Database Management
Abstract-- The ultimate goal of the Intelligent Travel Assistant (ITA) is the fusion and development of a number of technologies into a device that will increase the efficiency of our transportation network through increased use of mass transit and ride sharing. The ITA will include: a) dynamic ridesharing, b) spatio-temporal database management, c) wireless communications, and d) a management framework. The ITA itself is envisioned to be a compact portable device with the capability to plan multi-modal routes for its user. The traveler will enter a desired destination into the ITA and it will formulate several plans to get the user to this destination. The ITA will make use of wireless Internet technology to send and receive traffic information, transit schedules, and arrange for payment of fares. The Global Positioning System (GPS) will be used to track the user’s current position for use in route planning and also as a means of assessing traffic conditions while en-route. A spatio-temporal database management system will be used to efficiently track ITA positions in real-time. Index Terms—database systems, ride sharing, mobile communication, transportation
A framework for spatio%2Dtemporal query processing over wireless sensor networks.
Wireless sensor networks consist of nodes with the ability to measure, store, and process data, as well as to communicate wirelessly with nodes located in their wireless range. Users can issue queries over the network, e.g., retrieve information from nodes within a specified region, in applications such as environmental monitoring. Since the sensors have typically only a limited power supply, energy-efficient processing of the queries over the network is an important issue. In this paper, we introduce a general framework for distributed processing of spatio-temporal queries in a sensor network that has two main phases: (1) routing the query to the spatial area specified in the query; (2) collecting and processing the information from the nodes relevant to the query. Within this framework, different algorithms can be designed independently for each of the two phases. We also propose novel algorithms for this framework, one for the first phase and two for the second phase. In an extensive experimental evaluation we study the performance of these algorithms in terms of energy consumption, under varying conditions. The results allow us to recommend the most energy efficient solution, given a network and a spatiotemporal query. 1
Incremental and Effective Data Summarization for Dynamic Hierarchical Clustering.
Mining informative patterns from very large, dynamically changing databases poses numerous interesting challenges. Data summarizations (e.g., data bubbles) have been proposed to compress very large static databases into representative points suitable for subsequent effective hierarchical cluster analysis. In many real world applications, however, the databases dynamically change due to frequent insertions and deletions, possibly changing the data distribution and clustering structure over time. Completely reapplying both the data summarization and the clustering algorithm to detect the changes in the clustering structure and update the uncovered data patterns following such deletions and insertions is prohibitively expensive for large fast changing databases. In this paper, we propose a new scheme to maintain data bubbles incrementally. By using incremental data bubbles, a high-quality hierarchical clustering is quickly available at any point in time. In our scheme, a quality measure for incremental data bubbles is used to identify data bubbles that do not compress well their underlying data points after certain insertions and deletions. Only these data bubbles are re-built using efficient split and merge operations. An extensive experimental evaluation shows that the incremental data bubbles provide significantly faster data summarization than completely re-building the data bubbles after a certain number of insertions and deletions, and are effective in preserving (and in some cases even improving) the quality of the data summarization.
Automatic Extraction of Clusters from Hierarchical Clustering Representations.
Hierarchical clustering algorithms are typically more effective in detecting  the true clustering structure of a data set than partitioning algorithms.
Efficient Indexing of High Dimensional Normalized Histograms.
This paper addresses the problem of indexing high dimensional normalized histogram data, i.e., D-dimensional feature vectors H where sum(Hi)=1, i=1..D.These are often used as representations for multimedia objects in order to facilitate similarity query processing. By analyzing properties that are induced by the above constraint and that do not hold in general multi-dimensional spaces we design a new split policy.We show that the performance of similarity queries for normalized histogram data can be signi cantly improved by exploiting such properties within a simple indexing framework. We are able to process nearest-neighbor queries up to 10 times faster than the SR-tree and 3 times faster than the A-tree.
Automatic Extraction of Clusters from Hierarchical Clustering Representations.
Hierarchical clustering algorithms are typically more effective in detecting  the true clustering structure of a data set than partitioning algorithms.
Data Bubbles for Non%2DVector Data Speeding%2Dup Hierarchical Clustering in Arbitrary Metric Spaces.
To speed-up clustering algorithms, data summarization methods have been proposed, which first summarize the data set by computing suitable representative objects. Then, a clustering algorithm is applied to these representatives only, and a clustering structure for the whole data set is derived, based on the result for the representatives. Most previous methods are, however, limited in their application domain. They are in general based on sufficient statistics such as the linear sum of a set of points, which assumes that the data is from a vector space. On the other hand, in many important applications, the data is from a metric non-vector space, and only distances between objects can be exploited to construct effective data summarizations. In this paper, we develop a new data summarization method based only on distance information that can be applied directly to non-vector data. An extensive performance evaluation shows that our method is very effective in finding the hierarchical clustering structure of non-vector data using only a very small number of data summarizations, thus resulting in a large reduction of runtime while trading only very little clustering quality. 1.
Focused Co%2Dcitation Improving the Retrieval of Related Pages on the Web.

Analysis of SIGMOD%27s co%2Dauthorship graph.

Hierarchical cluster analysis of SAGE data for cancer profiling.
In this paper we present a method for clustering SAGE (Serial Analysis of Gene Expression) data to detect similarities and dissimilarities between different types of cancer on the subcellular level. The data, however, is extremely high dimensional, and due to the method of measurement, there are many errors as well as missing values in the data, challenging any clustering algorithm. Therefore, we introduce special pre-processing techniques to reduce these errors and to restore missing data. These techniques are tailored to the process that generates the data, making only very conservative changes. Furthermore, we present a new subspace selection technique to identify a relevant subset of attributes (genes) using the Wilcoxon test. This is a general technique that can be applied to select subspaces for the purpose of clustering whenever some high-level categories of interest are known for the data (such as cancerous and noncancerous) . Finally, we discuss the results of the application of the clustering algorithm OPTICS to the SAGE data, before and after our preprocessing steps.
Data Bubbles Quality Preserving Performance Boosting for Hierarchical Clustering.
In this paper, we investigate how to scale hierarchical clustering methods (such as OPTICS) to extremely large databases by utilizing data compression methods (such as BIRCH or random sampling). We propose a three step procedure: 1) compress the data into suitable representative objects; 2) apply the hierarchical clustering algorithm only to these objects; 3) recover the clustering structure for the whole data set, based on the result for the compressed data. The key issue in this approach is to design compressed data items such that not only a hierarchical clustering algorithm can be applied, but also that they contain enough information to infer the clustering structure of the original data set in the third step. This is crucial because the results of hierarchical clustering algorithms, when applied naively to a random sample or to the clustering features (CFs) generated by BIRCH, deteriorate rapidly for higher compression rates. This is due to three key problems, which we identify. To solve these problems, we propose an efficient post-processing step and the concept of a Data Bubble as a special kind of compressed data item. Applying OPTICS to these Data Bubbles allows us to recover a very accurate approximation of the clustering structure of a large data set even for very high compression rates. A comprehensive performance and quality evaluation shows that we only trade very little quality of the clustering result for a great increase in performance.
Multiple Similarity Queries A Basic DBMS Operation for Mining in Metric Databases.

Knowledge Discovery in Databases %2D Techniken und Anwendungen

Knowledge Discovery in Databases %2D Techniken und Anwendungen

Efficiently Supporting Multiple Similarity Queries for Mining in Metric Databases.
Metric databases are databases where a metric distance function is defined for pairs of database objects. In such databases, similarity queries in the form of range queries or k-nearest neighbor queries are the most important queries. In traditional query processing, single queries are issued independently by different users. In many data mining applications, however, the database is typically explored by iteratively asking similarity queries for answers of previous similarity queries. In this paper, we introduce a generic scheme for such data mining algorithms and we develop a method to transform such algorithms in a way that they can use multiple similarity queries, i.e. sets of queries issued simultaneously. We investigate two orthogonal approaches, reducing I/O cost as well as CPU cost, to speed-up the processing of multiple similarity queries. The proposed techniques apply to any type of similarity query and to an implementation based on an index or using a sequential scan. Parall...
Independent Quantization An Index Compression Technique for High%2DDimensional Data Spaces.
Two major approaches have been proposed to efficiently process queries in databases: Speeding up the search by using index structures, and speeding up the search by operating on a compressed database, such as a signature file. Both approaches have their limitations: Indexing techniques are inefficient in extreme configurations, such as high-dimensional spaces, where even a simple scan may be cheaper than an index-based search. Compression techniques are not very efficient in all other situations. We propose to combine both techniques to search for nearest neighbors in a high-dimensional space. For this purpose, we develop a compressed index, called the IQ-tree, with a three-level structure: The first level is a regular (flat) directory consisting of minimum bounding boxes, the second level contains data points in a compressed representation, and the third level contains the actual data. We overcome several engineering challenges in constructing an effective index structure of this type...
Fast Hierarchical Clustering Based on Compressed Data and OPTICS.
: One way to scale up clustering algorithms is to squash the data by some  intelligent compression technique and cluster only the compressed data records.  Such compressed data records can e.g. be produced by the BIRCH algorithm. Typically  they consist of the sufficient statistics of the form (N, X, X  2  ) where N is the  number of points, X is the (vector-)sum, and X  2  is the square sum of the points.  They can be used directly to speed up k-means type of clustering algorithms, but  it is not obvious how to use them in a hierarchical clustering algorithm. Applying  a hierarchical clustering algorithm e.g. to the centers of compressed subclusters  produces a very weak result. The reason is that hierarchical clustering algorithms  are based on the distances between data points and that the interpretaion of the  result relies heavily on a correct graphical representation of these distances. In this  paper, we introduce a method by which the sufficient statistics (N, X, X  2  ) of sub...
LOF Identifying Density%2DBased Local Outliers.
For many KDD applications, such as detecting criminal activities in E-commerce, finding the rare instances or the outliers, can be more interesting than finding the common patterns. Existing work in outlier detection regards being an outlier as a binary property. In this paper, we contend that for many scenarios, it is more meaningful to assign to each object a degree of being an outlier. This degree is called the local outlier factor (LOF) of an object. It is local in that the degree depends on how isolated the object is with respect to the surrounding neighborhood. We give a detailed formal analysis showing that LOF enjoys many desirable properties. Using realworld datasets, we demonstrate that LOF can be used to find outliers which appear to be meaningful, but can otherwise not be identified with existing approaches. Finally, a careful performance evaluation of our algorithm confirms we show that our approach of finding local outliers can be practical.  
Spatial Data Mining Database Primitives%2C Algorithms and Efficient DBMS Support.
: Spatial data mining algorithms heavily depend on the efficient processing of neighborhood relations since the neighbors of many objects have to be investigated in a single run of a typical algorithm. Therefore, providing general concepts for neighborhood relations as well as an efficient implementation of these concepts will allow a tight integration of spatial data mining algorithms with a spatial database management system. This will speed up both, the development and the execution of spatial data mining algorithms. In this paper, we define neighborhood graphs and paths and a small set of database primitives for their manipulation. We show that typical spatial data mining algorithms are well supported by the proposed basic operations. For finding significant spatial patterns, only certain classes of paths &#034;leading away&#034; from a starting object are relevant. We discuss filters allowing only such neighborhood paths which will significantly reduce the search space for spatial data mini...
Database Primitives for Spatial Data Mining.
: Spatial data mining algorithms heavily depend on the efficient processing of neighborhood relations since the neighbors of many objects have to be investigated in a single run of a typical algorithm. Therefore, providing general concepts for neighborhood relations as well as an efficient implementation of these concepts will allow a tight integration of spatial data mining algorithms with a spatial database management system. This will speed up both, the development and the execution of spatial data mining algorithms. In this paper, we define neighborhood graphs and paths and a small set of database primitives for their manipulation. Furthermore, we introduce neighborhood indices to speed up the processing of our database primitives. We implemented the database primitives on top of a commercial spatial database management system. The effectiveness and efficiency of the proposed approach was evaluated by using an analytical cost model and an extensive experimental study on a geographi...
Knowledge Discovery in Spatial Databases.
. Both, the number and the size of spatial databases, such as geographic  or medical databases, are rapidly growing because of the large amount of data obtained  from satellite images, computer tomography or other scientific equipment.  Knowledge discovery in databases (KDD) is the process of discovering valid,  novel and potentially useful patterns from large databases. Typical tasks for  knowledge discovery in spatial databases include clustering, characterization and  trend detection. The major difference between knowledge discovery in relational  databases and in spatial databases is that attributes of the neighbors of some object  of interest may have an influence on the object itself. Therefore, spatial  knowledge discovery algorithms heavily depend on the efficient processing of  neighborhood relations since the neighbors of many objects have to be investigated  in a single run of a typical algorithm. Thus, providing general concepts for  neighborhood relations as well as an eff...
Knowledge Discovery in Spatial Databases.
. Both, the number and the size of spatial databases, such as geographic  or medical databases, are rapidly growing because of the large amount of data obtained  from satellite images, computer tomography or other scientific equipment.  Knowledge discovery in databases (KDD) is the process of discovering valid,  novel and potentially useful patterns from large databases. Typical tasks for  knowledge discovery in spatial databases include clustering, characterization and  trend detection. The major difference between knowledge discovery in relational  databases and in spatial databases is that attributes of the neighbors of some object  of interest may have an influence on the object itself. Therefore, spatial  knowledge discovery algorithms heavily depend on the efficient processing of  neighborhood relations since the neighbors of many objects have to be investigated  in a single run of a typical algorithm. Thus, providing general concepts for  neighborhood relations as well as an eff...
Knowledge Discovery in Spatial Databases.
. Both, the number and the size of spatial databases, such as geographic  or medical databases, are rapidly growing because of the large amount of data obtained  from satellite images, computer tomography or other scientific equipment.  Knowledge discovery in databases (KDD) is the process of discovering valid,  novel and potentially useful patterns from large databases. Typical tasks for  knowledge discovery in spatial databases include clustering, characterization and  trend detection. The major difference between knowledge discovery in relational  databases and in spatial databases is that attributes of the neighbors of some object  of interest may have an influence on the object itself. Therefore, spatial  knowledge discovery algorithms heavily depend on the efficient processing of  neighborhood relations since the neighbors of many objects have to be investigated  in a single run of a typical algorithm. Thus, providing general concepts for  neighborhood relations as well as an eff...
OPTICS%2DOF Identifying Local Outliers.
For many KDD applications finding the outliers, i.e. the rare events, is  more interesting and useful than finding the common cases, e.g. detecting criminal  activities in E-commerce. Being an outlier, however, is not just a binary property. Instead, it
OPTICS%2DOF Identifying Local Outliers.
For many KDD applications finding the outliers, i.e. the rare events, is  more interesting and useful than finding the common cases, e.g. detecting criminal  activities in E-commerce. Being an outlier, however, is not just a binary property. Instead, it
Generalized Density%2DBased Clustering for Spatial Data Mining %28Abstract%29.

Towards the qualitative%2C plan%2Dbased simulation of international crises.

A Distribution%2DBased Clustering Algorithm for Mining in Large Spatial Databases.
The problem of detecting clusters of points belonging to a spatial point process arises in many applications. In this paper, we introduce the new clustering algorithm DBCLASD (Distribution Based Clustering of LArge Spatial Databases) to discover clusters of this type. The results of experiments demonstrate that DBCLASD, contrary to partitioning algorithms such as CLARANS, discovers clusters of arbitrary shape. Furthermore, DBCLASD does not require any input parameters, in contrast to the clustering algorithm DBSCAN requiring two input parameters which may be difficult to provide for large databases. In terms of efficiency, DBCLASD is between CLARANS and DBSCAN, close to DBSCAN. Thus, the efficiency of DBCLASD on large spatial databases is very attractive when considering
Algorithms for Characterization and Trend Detection in Spatial Databases.
  The number and the size of spatial databases, e.g. for geomarketing, traffic control or environmental studies, are rapidly growing which results in an increasing need for spatial data mining. In this paper, we present new algorithms for spatial characterization and spatial trend analysis. For spatial characterization it is important that class membership of a database object is not only determined by its non-spatial attributes but also by the attributes of objects in its neighborhood. In spatial trend analysis, patterns of change of some non-spatial attributes in the neighborhood of a database object are determined. We present several algorithms for these tasks. These algorithms were implemented within a general framework for spatial data mining providing a small set of database primitives on top of a commercial spatial database management system. A performance evaluation using a real geographic database demonstrates the effectiveness of the proposed algorithms. Furthermore, we show how the algorithms can be combined to discover even more interesting spatial knowledge.
Incremental Clustering for Mining in a Data Warehousing Environment.
Data warehouses provide a great deal of opportunities for performing data mining tasks such as classification and clustering. Typically, updates are collected and applied to the data warehouse periodically in a batch mode, e.g., during the night. Then, all patterns derived from the warehouse by some data mining algorithm have to be updated as well. Due to the very large size of the databases, it is highly desirable to perform these updates incrementally. In this paper, we present the first incremental clustering algorithm. Our algorithm is based on the clustering algorithm DBSCAN which is applicable to any database containing data from a metric space, e.g., to a spatial database or to a WWW-log database. Due to the density-based nature of DBSCAN, the insertion or deletion of an object affects the current clustering only in the neighborhood of this object. Thus, efficient algorithms can be given for incremental insertions and deletions to an existing clustering. Based on the formal definition of clusters, it can be proven that the incremental algorithm yields the same result as DBSCAN. A performance evaluation of IncrementalDBSCAN on a spatial database as well as on a WWW-log database is presented, demonstrating the efficiency of the proposed algorithm. IncrementalDBSCAN yields significant speed-up factors over DBSCAN even for large numbers of daily updates in a data warehouse. 
Density%2DBased Clustering in Spatial Databases The Algorithm GDBSCAN and Its Applications.

Clustering for Mining in Large Spatial Databases.

Density%2DConnected Sets and their Application for Trend Detection in Spatial Databases.
  Several clustering algorithms have been proposed for class identification in spatial databases such as earth observation databases. The effectivity of the well-known algorithms such as DBSCAN, however, is somewhat limited because they do not fully exploit the richness of the different types of data contained in a spatial database. In this paper, we introduce the concept of density-connected sets and present a significantly generalized version of DBSCAN. The major properties of this algorithm are as follows: (1) any symmetric predicate can be used to define the neighborhood of an object allowing a natural definition in the case of spatially extended objects such as polygons, and (2) the cardinality function for a set of neighboring objects may take into account the non-spatial attributes of the objects as a means of assigning application specific weights. Density-connected sets can be used as a basis to discover trends in a spatial database. We define trends in spatial databases and show how to apply the generalized DBSCAN algorithm for the task of discovering such knowledge. To demonstrate the practical impact of our approach, we performed experiments on a geographical information system on Bavaria which is representative for a broad class of spatial databases.
Spatial Data Mining A Database Approach.
Knowledge discovery in databases (KDD) is an important task in spatial  databases since both, the number and the size of such databases are rapidly  growing. This paper introduces a set of basic operations which should be supported  by a spatial database system (SDBS) to express algorithms for KDD in  SDBS. For this purpose, we introduce the concepts of neighborhood graphs and  paths and a small set of operations for their manipulation. We argue that these operations  are sufficient for KDD algorithms considering spatial neighborhood relations  by presenting the implementation of four typical spatial KDD algorithms  based on the proposed operations. Furthermore, the efficient support of operations  on large neighborhood graphs and on large sets of neighborhood paths by the  SDBS is discussed. Neighborhood indices are introduced to materialize selected  neighborhood graphs in order to speed up the processing of the proposed operations.
A Density%2DBased Algorithm for Discovering Clusters in Large Spatial Databases with Noise.
Clustering algorithms are attractive for the task of class identification in spatial databases. However, the application to large spatial databases rises the following requirements for clustering algorithms: minimal requirements of domain knowledge to determine the input parameters, discovery of clusters with arbitrary shape and good efficiency on large databases. The well-known clustering algorithms offer no solution to the combination of these requirements. In this paper, we present the new clustering algorithm DBSCAN relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape. DBSCAN requires only one input parameter and supports the user in determining an appropriate value for it. We performed an experimental evaluation of the effectiveness and efficiency of DBSCAN using synthetic data and real data of the SEQUOIA 2000 benchmark. The results of our experiments demonstrate that (1) DBSCAN is significantly more effective in discovering clusters of arbitrary shape than the well-known algorithm CLAR-ANS, and that (2) DBSCAN outperforms CLARANS by a factor of more than 100 in terms of efficiency.
